package 剑指offer.Month7_07.day12;

public class 机器人的运动范围 {
    int row = 0;
    int col = 0;
    public int movingCount(int threshold, int rows, int cols) {
        boolean[][] arr = new boolean[rows][cols];
        row = rows;
        col = cols;
        int count = dfs(0,0,arr,threshold);
        return count;
    }


    public int dfs(int rows,int cols,boolean[][] arr,int threshold){
        if(rows < 0 || rows >= row || cols < 0 || cols >= col || arr[rows][cols] || solve(rows) + solve(cols) > threshold){
            return 0;
        }
        arr[rows][cols] = true;
        return 1 + dfs(rows + 1,cols,arr,threshold) + dfs(rows - 1,cols,arr,threshold)
                + dfs(rows,cols + 1,arr,threshold) + dfs(rows,cols - 1,arr,threshold);
    }

    public int solve(int num){
        int res = 0;
        while(num > 0){
            res += num % 10;
            num /= 10;
        }
        return res;
    }
}
